
#ifndef __VOL_LIP_H__
#define __VOL_LIP_H__

#include <sys/types.h>
#include "vol_lippar.h"

/*The type of very long ints.*/
typedef long * verylong;

#define FREE

#ifdef FREE
#define STATIC
#define FREESPACE(x)    zfree(&x);
#define FREE2SPACE(x,y) zfree(&x); zfree(&y);
#define FREE3SPACE(x,y,z) zfree(&x); zfree(&y); zfree(&z);
#else
#define STATIC          static
#define FREESPACE(x)
#define FREE2SPACE(x,y) 
#define FREE3SPACE(x,y,z)
#endif

#define ILLEGAL 0


#ifdef NO_ALLOCATE
# define ALLOCATE 0
#else
# define ALLOCATE 1
#endif

#ifdef PRT_REALLOC
# undef PRT_REALLOC
# define PRT_REALLOC 1
#else
# define PRT_REALLOC 0
#endif

#ifndef CHARL
# define CHARL           8      /* 8 bits per char */
#endif

#ifndef SIZEOFLONG
# define SIZEOFLONG      4      /* set this to sizeof(long) */
#endif

#define BITSOFLONG      (CHARL*SIZEOFLONG)

#ifdef ALPHA
# ifdef ALPHA50
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# ifndef PLAIN
#  undef KARAT
#  define KARAT  1
# endif
# ifdef SINGLE_MUL
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# define NBITS          62
# undef BITSOFLONG
# define BITSOFLONG     64
# undef  SIZEOFLONG
# define SIZEOFLONG      8
# define PRIM_BND      (1L<<14)
# define ALPHA_OR_ALPHA50       1
#endif

#ifdef ALPHA50
# ifndef PLAIN
#  undef KARAT
#  define KARAT  1
# endif
# ifdef SINGLE_MUL
#  undef ILLEGAL
#  define ILLEGAL	1
# endif
# define NBITS          62
# undef BITSOFLONG
# define BITSOFLONG     64
# undef  SIZEOFLONG
# define SIZEOFLONG      8
# define PRIM_BND      (1L<<14)
# define ALPHA50NBITS   50
# define ALPHA50NBITSH  (ALPHA50NBITS>>1)
# define ALPHA50RADIX   (1L<<ALPHA50NBITS)
# define        ALPHA50RADIXM   (ALPHA50RADIX-1)
# define        ALPHA50RADIXROOT        (1L<< ALPHA50NBITSH)
# define ALPHA50RADIXROOTM      (ALPHA50RADIXROOT-1)
# define ALPHA_OR_ALPHA50       1
#endif


#ifdef PLAIN
# define PLAIN_OR_KARAT  1
#endif

#ifdef KARAT
# define PLAIN_OR_KARAT  1
#endif


#ifndef NBITS
# ifdef SINGLE_MUL
#  define NBITS        26
# else
#  define NBITS         30
# endif
#endif

#define NBITSH          (NBITS>>1)
#define RADIX           (1L<<NBITS)
#define RADIXM          (RADIX-1)
#define RADIXROOT       (1L<<NBITSH)
#define RADIXROOTM      (RADIXROOT-1)

#ifndef SIZE
# define SIZE           20      /* SIZE*NBITS must be >= BITSOFLONG */
#endif


#ifndef OUT_LINE
# define OUT_LINE       68      /* approximate bound # digits per line */
#endif

#define OUT_LINE_BREAK  '\\'

#ifndef IN_LINE
# define IN_LINE      2048      /* at most 2048 characters per line */
#endif

#define IN_LINE_BREAK   '\\'

#ifndef HEX_BLOCK
# define HEX_BLOCK	8
#endif

#ifndef HEX_BLOCKS_PER_LINE
# define HEX_BLOCKS_PER_LINE	7
#endif

#define HEX_SEP_CHAR	' '

#ifndef PRIM_BND
# ifdef SINGLE_MUL
#  define PRIM_BND      (1L<<14)
# else
#  define PRIM_BND      (1L<<(NBITSH-1))
# endif
                        /* to generate primes <= (2*PRIM_BND+1)^2 */
                        /* last prime for NBITS == 30 is 1073807359 */
			/* same for SINGLE_MUL */
#elif (PRIM_BND>(1L<<(NBITSH-1)))
# undef PRIM_BND
# define PRIM_BND       (1L<<(NBITSH-1))
#endif

#define PRIM_UP         ((((PRIM_BND<<1)+1)*((PRIM_BND<<1)+1))-(NBITS<<2))

#if (NBITS&1)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (NBITS <= 0)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (NBITS >= BITSOFLONG)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#if (SIZE*NBITS<=BITSOFLONG)
# undef ILLEGAL
# define ILLEGAL 1
#endif

#ifdef SINGLE_MUL
# if (NBITS != 26)
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
# ifdef PLAIN
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
# ifdef KARAT
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
#endif

#ifdef PLAIN
# ifdef KARAT
#  undef ILLEGAL
#  define ILLEGAL 1
# endif
#endif

#ifdef __cplusplus
extern "C" {
#endif

/******************************************************************************\
*   Internal macros
*
*   Although the package is supposed to be portable, you might want to
*   fine tune it to your particular machine to get better performance.
*   The easiest way to do this is to replace the following macros, which
*   you will find in the source code, by appropriate assembly language
*   versions:
*
*   Also the C-code for zsubmul, zdiv21 and zmulmods can be made
*   much faster in a similar way. I always simply used the macros
*   or the C-code, and I get acceptable performance.
\******************************************************************************/

    static void zaddmulp(long *a, long b, long d, long *t);
        /******************************************************************\
        * a = (a + t + b * d) % RADIX; and simultaneously
        * t = (a + t + b * d) / RADIX;
        \******************************************************************/

    static void zaddmulpsq(long *a, long b, long *t);
        /******************************************************************\
        * a = (a + b * b) % RADIX; and simultaneously
        * t = (a + b * b) / RADIX;
        \******************************************************************/

    static void zaddmulone(verylong a, verylong b);
        /******************************************************************\
        * a += b;
        * a and b not at overlapping addresses
        \******************************************************************/

    static void zaddmul(long d, verylong a, verylong b);
        /******************************************************************\
        * a += d * b;
        * a and b not at overlapping addresses (except if d=1)
        \******************************************************************/

    static void zaddmulsq(long d, verylong a, verylong b);
        /******************************************************************\
        * a += b[0] * b[1:d];
        * a and b not at overlapping addresses (except if d=1)
        \******************************************************************/


/******************************************************************************\
*  Basic functions
*  
*  Addition, subtraction, multiplication, squaring, and
*  division with remainder on signed arbitrary length integers.
*  Multiplication and squaring use Karatsuba, if inputs large enough;
*  see KAR_MUL_CROV, KAR_SQU_CROV, and KAR_DEPTH as explained above.
\******************************************************************************/

    void zstart(void);
        /******************************************************************\
        * To initialize some global machine dependent values
        * that have to be computed only once, call this only once per run.
        * Everything still works fine if you forget to call zstart.
        * If you`re sure that you`re not going to forget it, you may
        * compile the package with the -DSTART flag and get slightly
        * faster code.
        *
        * possible error message:
        *   recompile with smaller NBITS
        * result undefined if error occurs
        \******************************************************************/

    void zsadd(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = a + d;
        * 
        \******************************************************************/

    void zadd(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a + b;
        * 
        \******************************************************************/

    void zsub(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a - b;
        * 
        \******************************************************************/

    void zsubpos(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a - b;
        * 
        * only for a >= b >= 0
        \******************************************************************/

    void zsmul(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = d * a;
        * 
        \******************************************************************/

    void zmul(verylong a, verylong b, verylong *c);
        /******************************************************************\
        * *c = a * b;
        * 
        * output cannot be input
        \******************************************************************/

    void zmulin(verylong a, verylong *b);
        /******************************************************************\
        * *b = a * b;
        * 
        * output cannot be input
        \******************************************************************/

    void zsq(verylong a, verylong *c);
        /******************************************************************\
        * *c = a * a;
        * 
        * output cannot be input
        \******************************************************************/

    long zsdiv(verylong a, long d, verylong *b);
        /******************************************************************\
        * *b = a / d;
        * return (a % d);
        * 
        * d != 0,
        * always b * q + (a % d) == a and,
        * unless b divides a, sign(a % d) == sign(d),
        * calls zdiv if |d| >= RADIX
        *
        * possible error message:
        *   division by zero in zsdiv
        * result undefined if error occurs
        \******************************************************************/

    void zdiv(verylong a, verylong b, verylong *q, verylong *r);
        /******************************************************************\
        * *q = a / b;
        * *r = a % b;
        * 
        * b != 0,
        * always b * q + r == a,
        * unless b divides a, sign(r) == sign(b)
        *
        * possible error message:
        *   division by zero in zdiv
        * result undefined if error occurs
        \******************************************************************/

    void zmod(verylong a, verylong b, verylong *r);
        /******************************************************************\
        * *r = a % b;
        * 
        * unless b divides a, sign(r) == sign(b),
        * slightly faster than zdiv
        *
        * possible error message:
        *   division by zero in zmod
        * result undefined if error occurs
        \******************************************************************/


/******************************************************************************\
*  Shifting and bit manipulation
*
*  Left and right shifting, removal of all factors 2,
*  parity test, logical and/(x)or, bit selections, weight,
*  concatenation, bit-reverse
*
*  WARNING: The bit manipulation routines need to be debugged carefully
\******************************************************************************/

    void z2mul(verylong n, verylong *a);
        /******************************************************************\
        * *a = 2 * n;
        * 
        \******************************************************************/

    long z2div(verylong n, verylong *a);
        /******************************************************************\
        * *a = n / 2; return (n % 2);
        * 
        * warning: for n == -2 * k + 1 (k > 0), z2div(n, &a)
        * gives a = -k + 1, but zsdiv(a, 2, &b) gives b = -k,
        * both return 1
        \******************************************************************/

    long z2mod(verylong n);
        /******************************************************************\
        * return (n % 2);
        \******************************************************************/

    void zlshift(verylong n, long k, verylong *a);
        /******************************************************************\
        * *a = 2 ^ k * n;
        * 
        * i.e., shifts left over k positions,
        * calls zrshift(n, -k, a) if k < 0
        \******************************************************************/

    void zrshift(verylong n, long k, verylong *a);
        /******************************************************************\
        * *a = n / (2 ^ k);
        * 
        * i.e., shifts right over k positions,
        * calls zlshift(n, -k, a) if k<0
        \******************************************************************/
    
/******************************************************************************\
*  Comparison, signs, copying, logarithms
\******************************************************************************/

    long zcompare(verylong a, verylong b);
        /******************************************************************\
        * if (a > b)
        *     return (1);
        * if (a == b)
        *     return (0);
        * if (a < b)
        *     return (-1);
        \******************************************************************/

    void znegate(verylong *a);
        /******************************************************************\
        * *a = -a;
        * 
        * has no effect on zero a
        \******************************************************************/

    void zcopy(verylong a, verylong *b);
        /******************************************************************\
        * *b = a;
        \******************************************************************/

/******************************************************************************\
*  Conversion
*
*  Conversion between very long ints and ordinary longs or doubles.
*  Conversion for very long ints to arbitrary basis and back.
\******************************************************************************/
        
    void zzero(verylong *a);
        /******************************************************************\
        * *a = 0;
        * 
        * allocated zero
        \******************************************************************/

    void zone(verylong *a);
        /******************************************************************\
        * *a = 1;
        * 
        \******************************************************************/

    void zintoz(long d, verylong *a);
        /******************************************************************\
        * *a = d;
        * 
        \******************************************************************/

    long ztoint(verylong a);
        /******************************************************************\
        * return (attempted conversion of a`s value to long);
        * no overflow check
        * 
        \******************************************************************/

/******************************************************************************\
*  Modular arithmetic 
*  
*  Addition, subtraction, multiplication, squaring division, inversion,
*  and exponentiation modulo a positive modulus n, where all operands
*  (except for the exponent in exponentiation) and results are in the
*  range [0, n-1]. For heavy computations modulo a fixed modulus it
*  might be better to use Montgomery arithmetic.
\******************************************************************************/

    void zmulmod(verylong a, verylong b, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a * b) % n;
        * 
        * with 0 <= a,b,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zmulmod
        * result undefined if error occurs
        \******************************************************************/

    void zsqmod(verylong a, verylong n, verylong *c);
        /******************************************************************\
        * *c = (a ^ 2) % n;
        * 
        * with 0 <= a,c < n (and n positive)
        *
        * possible error message:
        *   modulus zero in zsqmod
        * result undefined if error occurs
        \******************************************************************/

    long zinv(verylong ain,	verylong nin, verylong *invv);
    void zexpmod(verylong a, verylong e, verylong n, verylong *b);
        /******************************************************************\
        * *b = (a ^ e) % n;
        * 
        * a and b can be the same, but both unequal
        * to e and n, (a^(-e)) and n coprime if e negative
        *
        * possible error message:
        *   modulus zero in zexpmod
        *   undefined quotient in zexpmod       (caused by negative exponent)
        * result undefined if error occurs, except if the quotient
        * is undefined, in which case a factor of n will be returned in b
        * (of course, only if the -DNO_HALT flag is used)
        \******************************************************************/

/******************************************************************************\
*  Allocation
\******************************************************************************/

    // void zsetlength(verylong *v, long len, char *str);
    void zsetlength(verylong *v, long len);
        /******************************************************************\
        * (re)allocates enough space for v to hold an integer of
        * absolute value < 2 ^ (len * RADIX), uses SIZE instead of len if
        * len < SIZE, use this to allocate space by hand (if you`re using
        * the -DNO_ALLOCATE flag), don`t use this unless you know what you`re
        * doing
        *
        * possible error messages:
        *   reallocation failed in zsetlength         (out of space)
        *   allocation failed in zsetlength           (out of space)
        *   negative size allocation in zsetlength    (*x==0 and len<0,
        *          ====> BUG if you didn`t call zsetlength yourself)
        * result undefined if error occurs
        \******************************************************************/

    void zfree(verylong *x);
        /******************************************************************\
        * frees the memory allocated for x, and sets x back to 0,
        * where x is a very long int allocated by the functions internally
        * or by zsetlength, use this to free the memory of very long ints
        * which are local to functions (unless the locals are static)
        \******************************************************************/

/******************************************************************************\
*  Input and output 
*
*       Functions for (hexa)decimal/direct in/output from/to files,
*       stdin/stdout, or strings
\******************************************************************************/

    void zhsread(char *str, verylong *a);
        /******************************************************************\
        * reads hexadecimal representation of very long int from string str
        * into a, format as in zhfread
        \******************************************************************/

    void zhswrite(char *str, verylong a);

    void free_karmem ();

#ifdef __cplusplus
}
#endif

#endif

